import java.util.*;

public class Test {
    public static void main(String[] args) {
        String ss = "abcde";
        System.out.println();
        StringBuilder s = new StringBuilder();


    }
    public String finalString(String s) {
        //利用双端队列
        Deque<Character> deque = new ArrayDeque<>();
        //定义一个布尔类型head，每次遇到 i 就取反
        boolean head = true;

        for (int i = 0; i < s.length(); i++) {
            //遇到 i head取反
            char ch = s.charAt(i);
            if (ch == 'i') {
                head = !head;
                continue;
            }

            if (head) {
                //刚开始就正常按照队列的形式插入
                deque.offerLast(ch);
            } else {
                deque.offerFirst(ch);
            }
        }

        //如果head是true则将结果正序输出
        //否则逆序数粗
        StringBuilder sb = new StringBuilder();
        for (char x : deque) {
            sb.append(x);
        }

        if (!head) {
            sb.reverse();//反向输出
        }

        return sb.toString();
    }
    public static void main4(String[] args) {
        Deque<Character> deque = new ArrayDeque<>();
        boolean head = true;
        System.out.println(!head);
    }
    public static void main3(String[] args) {
        String original = "Hello,CWorld!";
        //相当于翻转从 7-11的下标
        String reversed = reverseSubstring(original, 7, 12);
        System.out.println(reversed); // Output: World ,olleH
    }

    public static String reverseSubstring(String str, int startIndex, int endIndex) {
        if (str == null || str.isEmpty() || startIndex < 0 || endIndex >= str.length() || startIndex >= endIndex) {
            return str;
        }

        char[] chars = str.toCharArray();
        while (startIndex < endIndex) {
            char temp = chars[startIndex];
            chars[startIndex] = chars[endIndex];
            chars[endIndex] = temp;
            startIndex++;
            endIndex--;
        }

        return new String(chars);
    }
    static List<List<Integer>> res = new ArrayList<>();
    static List<Integer> path = new LinkedList<>();
    public static void main2(String[] args) {
        for (int i = 0; i < 3; i++) {
            getIt();
        }
        System.out.println(res);
        List<Integer> aaa = new LinkedList<>();

    }

    public static void getIt() {
        for (int i = 0; i < 2; i++) {
            explain(i);
        }
        res.add(path);
    }
    public static void explain(int i) {
        path.add(i);
    }
    public static void main111(String[] args) {
        String a = "abc";
        System.out.println(a.substring(1,3));
        String s = "MCMXCIV";
        System.out.println(romanToInt(s));
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);
        System.out.println(queue.peek());
        queue.poll();
        Stack<Integer> stack = new Stack<>();
        stack.push(1);
        stack.add(2);
        for (int x : stack) {
            System.out.print(x + " ");
        }
        stack.pop();



    }

    public boolean isValid(String s) {
        //利用栈来完成
        Stack<Character> stack = new Stack<>();
//        while (i < s.length()) {
//            if (stack.isEmpty() && ch == ')' || ch == '}' || ch == ']') {
//                return false;
//            }
//            stack.push(ch);
//            i++;
//            ch = s.charAt(i);
//            char tmp = stack.peek();
//            if (ch == '}' && tmp == '{' || ch == ']' && tmp == '['
//                || ch == ')' && tmp == ')') {
//                //此时弹出栈顶元素
//                stack.pop();
//            }
//        }


        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == '(' || ch == '[' || ch == '{') {
                //因为从第一个开始
                //所以先判断是否符合条件之后入栈
                stack.push(ch);
            } else {
                if (stack.isEmpty()) {
                    return false;
                }
                //先看栈顶元素
                char ch2 = s.charAt(i);
                if (ch2 == '{' && ch == '}' || ch2 == '(' && ch == ')' || ch2 == '[' && ch == ']') {
                    //此时进行出栈
                    stack.pop();
                } else {
                    return false;
                }

            }
        }
        return true;
    }

    public static int romanToInt(String s) {
        //题目给出特殊情况只有6种
        //所以我们利用 key - value 模型
        //直接利用Map来将这六种特殊情况存储到Map中去
        Map<String, Integer> map = new TreeMap<>();
        map.put("IV", 4);
        map.put("IX", 9);
        map.put("XL", 40);
        map.put("XC", 90);
        map.put("CD", 400);
        map.put("CM", 900);

        //剩余可以直接判断
        int i = 0;
        int res = 0;
        while (i < s.length()) {
            //因为可能会越界，所以需要判断一下
            //截取字符串
            if (i + 1 < s.length()) {
                String tmp = s.substring(i, i + 2);
                //因为是左闭右开
                if (map.containsKey(tmp)) {
                    //如果包含
                    res += map.get(tmp);
                    i += 2;
                } else {
                    char ch = s.charAt(i);
                    if (ch == 'I') {
                        res += 1;
                    } else if (ch == 'V') {
                        res += 5;
                    } else if (ch == 'X') {
                        res += 10;
                    } else if (ch == 'L') {
                        res += 50;
                    } else if (ch == 'C') {
                        res += 100;
                    } else if (ch == 'D') {
                        res += 500;
                    } else if (ch == 'M') {
                        res += 1000;
                    }
                    i++;
                }
            } else {

                char ch = s.charAt(i);
                if (ch == 'I') {
                    res += 1;
                } else if (ch == 'V') {
                    res += 5;
                } else if (ch == 'X') {
                    res += 10;
                } else if (ch == 'L') {
                    res += 50;
                } else if (ch == 'C') {
                    res += 100;
                } else if (ch == 'D') {
                    res += 500;
                } else if (ch == 'M') {
                    res += 1000;
                }
                i++;
            }
        }

        return res;
    }
}
